package DataStructure.stack.swordOffer2;

import DataStructure.linkList.ListNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 剑指 Offer 06. 从尾到头打印链表 https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
 */
public class ReversePrint {

    /**
     * 思路一：递归法
     */
    public int[] reversePrint(ListNode head) {
        List<Integer> result = new ArrayList<>();
        reverseAdd(head, result);
        int[] nums = new int[result.size()];
        for(int i = 0;i < nums.length;i++) {
            nums[i] = result.get(i);
        }
        return nums;
    }
    private void reverseAdd(ListNode head, List<Integer> result) {
        if(head == null) return;
        reverseAdd(head.next, result);
        result.add(head.val);
    }

    /**
     * 思路二：辅助栈法
     */
    public int[] reversePrint2(ListNode head) {
        LinkedList<Integer> stack = new LinkedList<Integer>();
        while(head != null) {
            stack.addLast(head.val);
            head = head.next;
        }
        int[] res = new int[stack.size()];
        for(int i = 0; i < res.length; i++)
            res[i] = stack.removeLast();
        return res;
    }

}
